//Cracking the coding interview (5ed), 2_1
//Write code to remove deduplicate an unsorted linked list.
//FOLLOW UP
// How would you solve this problem if a temporary buffer is not allowed?
//5:37PM--5:51PM(bugfree)

#include<iostream>
#include<deque>
#include<unordered_set>
using namespace std;

struct Node {
	Node():l(NULL), r(NULL) {}
	int key;
	Node *l, *r;
};

struct List {
	List():head(NULL) {}
	Node *head;
};

void DeDuplicate(List &iList) 
{
	unordered_set<int> uset;
	if(!iList.head) return;
	Node *p = iList.head;
	while(p) {
		if (uset.find(p->key) == uset.end()) {
			uset.insert(p->key);
			p = p->r;
		} else {
			Node *prev = p->l;
			Node *after = p->r;
			prev->r = after;
			if(after) 
                          after->l = prev;
			//delete p;	//may have problem!
			p = after;
		}
	}
}

//5:52PM--5:58PM--6:04PM(bugfree)
void DeDuplicate2(List &iList) 
{
	Node *p1, *p2;
	if(!iList.head) return;
	p1 = iList.head;
	p2 = p1->r;
	while(p1) {
		while(p2) {
			if(p2->key == p1->key) {
				Node *p3 = p2;
				p1->r = p2->r;
				p2 = p2->r;
				if(p2) 
                                  p2->l = p1;
				//delete p3; // may have problem
			} else {
				p2 = p2->r;
			}
		}
		p1 = p1->r;
		if(p1) 
                  p2 = p1->r;
	}
}

int main(int argc, char *argv[]) 
{
	Node *list = new Node[6];

	for (int i = 0; i < 6; i++) {
		list[i].key = i;
		if(i) 
		  list[i].l=&list[i-1];
		if(i!=5)
		  list[i].r=&list[i+1];
	}

	list[3].key = 4;
	List list0;
	list0.head = &list[0];
	DeDuplicate2(list0);

	return 0;
}
